package org.aplombh.java.leetcode.all;

import java.util.*;

public class _15三数之和 {
    public static void main(String[] args) {
        System.out.println(new Solution15_2().threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
    }
}

// 暴力
class Solution15_1 {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> arrayLists = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if (i != j && j != k && i != k && nums[i] + nums[j] + nums[k] == 0) {

                        List<Integer> integers = new ArrayList<>();
                        integers.add(nums[i]);
                        integers.add(nums[j]);
                        integers.add(nums[k]);

                        boolean flag = true;
                        Integer[] ints1 = integers.toArray(new Integer[0]);
                        Arrays.sort(ints1);
                        for (List<Integer> arrayList : arrayLists) {
                            Integer[] ints2 = arrayList.toArray(new Integer[0]);
                            Arrays.sort(ints2);
                            if (Arrays.equals(ints1, ints2)) {
                                flag = false;
                                break;
                            }
                        }
                        if (flag)
                            arrayLists.add(integers);
                    }
                }
            }
        }
        return arrayLists;
    }
}

// 双指针
class Solution15_2 {
    public List<List<Integer>> threeSum(int[] nums) {

        int n = nums.length;
        Arrays.sort(nums);

        List<List<Integer>> ans = new ArrayList<>();

        for (int i = 0; i < n; i++) {

            if (nums[i] > 0) break;

            // 从第二个开始去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int first = nums[i];
            int target = -first;

            // 目标 从j 到k 找到两个相加值等于target的两个值

            for (int j = i + 1, k = n - 1; j < k; ) {

                // 从第二个开始去重

                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    j++;
                    continue;
                }

                if (k < n - 1 && nums[k] == nums[k + 1]) {
                    k--;
                    continue;
                }


                int second = nums[j];
                int third = nums[k];

                if (second + third == target) {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(first);
                    list.add(second);
                    list.add(third);
                    ans.add(list);
                    // 接着往下走
                    j++;
                } else if (second + third < target) {
                    j++;
                } else {
                    k--;
                }
            }
        }
        return ans;
    }
}

